Bucket Sort
#Algorithm #Algorithm-Bucket_Sort #정렬 #분배정렬
1. Bucket Sort
Bucket Sort Wiki
=> 양동이에 데이터(혹은 데이터들)를 담아 정렬하는 방법
1-1. 버킷 정렬의 키워드 요소
- 버킷
- 버킷에 나눠담는 로직
- 버킷 내부를 정렬하는 로직
- 모든 버킷 안의 데이터를 하나로 합치는 로직
위의 4가지 중 버킷 안의 데이터를 하나로 합치는 로직이 있으면 정렬이 완수되는 것이지만, 합치다 말면 select가 된다. (quickSelect와 같은 선택알고리즘이 된다.)
1-2. 양동이에 왜 담아?
세가지 정도를 위한것 같다.
- 그룹화 정렬 정도로 정렬이 만족될 때
- 각 버킷 내의 데이터들을 정렬해두고, 모든 버킷들의 데이터들을 통으로 정렬할 때
- 양동이가 정렬 자체가 될 때
1. 그룹화 정렬 정도로 정렬이 만족될 때
"10단위로 끊어서 분류하고 그중에서 데이터가 제일 없는 단위를 알고싶어"
위의 생각을 구현하기 위해 사용하는것도 버킷정렬이다.
2. 각 버킷 내의 데이터들을 정렬해두고, 모든 버킷들의 데이터들을 통으로 정렬할 때
가장 일반적으로 이론설명에 등장하는 유즈케이스 아닐까.
버킷 내의 데이터를 정렬하기 위해서는 다른 정렬 알고리즘을 사용한다. (퀵이나 하이브리드나...)
보통의 정렬은 재귀적 호출이 일어나 데이터의 정렬 시작과 끝 이후에 데이터를 조작할 수 있지만, 버킷정렬은 데이터 조작이 들어갈 틈이 생긴다는점을 주목해야 할 것 같다. (여기서 조작이란, 데이터를 변조시키는게 아니라 데이터를 가지고 확인하거나 하는 모든것을 의미한다.)
예를들어, "10만개 데이터중에 가장 높은 수치를 나타내는 1000개의 데이터셋을 찾고싶어. 근데 데이터는 0-1범위이고, 수치는 보통 0.4정도에 가장 많이 몰려있는데 0.85 이상으로는 잘 안가는걸로 알고있어." 라고 해보자. 여기서 우린 어떤 정렬을 쓰면 좋을까? 처음부터 모든 데이터를 정렬할 것인가? 1-0.9, 0.8-0.7, 0.7-0.6 ..., 0.1-0 으로 범위를 나누고 1-0.9 양동이부터 안의 데이터가 몇개인지 살펴보고 1000번째 데이터가 있을 그 양동이만 정렬하는게 유리하지 않을까?
3. 양동이가 정렬 자체가 될 때
양동이의 라벨이(보통은 배열의 인덱스) 정렬 자체를 나타내는 경우이다.
2.에서 내부 정렬이 필요없는 경우를 의미할 수 있다.
다른 경우는 양동이에 데이터를 하나씩 담는 경우이다. bucket[countingMap.get(countingKey)] = countingKey
이렇게 하면 키가 카운팅된 수가 양동이의 인덱스가 되어 정렬이된다.
1-3. 장단점
구간을 나눌 수 있다는 데에 장점이 있다.
단점이라면 양동이를 만들기 위한 공간복잡도가 클 수도 있다는 점.
2. 구현
2-1. 자료구조
양동이는 배열, 양동이 내부는 리스트정도로 만드는 것 같다.
2-2. 알고리즘
val nums = arrayOf(1,3,14,15,29,30,88,48,75) //1-100까지의 수
val bucket: Array<ArrayList<Int>> = Array<ArrayList<Int>>(11){ArrayList<Int>()}
//그룹화
for(num in nums) {
bucket[num/10].add(num)
}
println("${bucket.contentToString()}")
//그룹 내 정렬
for((index, bucketItems) in bucket.withIndex()) {
bucket[index] = quickSort(bucketItems) //임의의 알고리즘
}
//전체 정렬
val sortedList: ArrayList<Int> = ArrayList<Int>()
for(bucketItems in bucket) {
for (item in bucketItems) {
sortedList.add(item)
}
}